public class IntegerBreak {
    // https://leetcode.cn/problems/integer-break/
    class Solution {
        public int integerBreak(int n) {

            // // 先不用动态规划试试
            // if(n == 2) return 1;
            // if(n == 3) return 2;
            // if(n == 4) return 4;

            // int count1 = n / 3;
            // int rest = n % 3;
            // if(rest == 0)
            // {
            //     return (int)Math.pow(3,count1);
            // }
            // if(rest == 1){
            //     count1--;
            //     rest = 4;
            //     return (int)rest * (int)Math.pow(3,count1);
            // }
            // return (int)rest * (int)Math.pow(3,count1);

            // 动态规划的做法
            // dp[i]: 表示整数为i的数凑成的最大乘积
            if(n  == 2) return 1;
            if(n == 3) return 2;
            if(n == 4) return 4;
            int [] dp = new int[n+1];
            if(n >= 5){

                dp[0] = 1;
                dp[1] = 1;
                dp[2] = 2;
                dp[3] = 3;
                dp[4] = 4;
                for(int i = 5 ; i <= n ; i ++)
                {
                    int time = i % 3;
                    if(time == 0)
                    {
                        dp[i] = dp[i-3] * 3;
                    }else if(time == 1)
                    {
                        dp[i] = dp[i-4] * 4;
                    }else if(time == 2)
                    {
                        dp[i] = dp[i-2] * 2;
                    }
                    //System.out.println(i + " " + dp[i]);

                }

            }
            return dp[n];



        }
    }
}
